package arithmetic2.day10;

import java.util.Arrays;

/*
   kmp算法
 */
public class Kmp {
    public static void main(String[] args) {
//        System.out.println(Arrays.toString(getNext("adbsjadkladbsjadk2"))); // -1 0 0 0 0 1 2
        System.out.println(indexOf("abafjdlkf", "jdlk"));
    }

    /*
        kmp算法
     */
    public static int indexOf(String str1, String str2) {
        int i1 = 0;
        int i2 = 0;
        char[] cs1 = str1.toCharArray();
        char[] cs2 = str2.toCharArray();
        int[] next = getNext(str2);
        while (i1 < cs1.length && i2 < cs2.length) {
            if (cs1[i1] == cs2[i2]) {   //在相同的的地方两个指针后移
                i1++;
                i2++;
            } else if (next[i2] == -1) {   //当两个字符不相等，并且i2之前的字符串最长前缀和最长后缀为0时（代表i2==0），i1后移
                i1++;
            } else {
                i2 = next[i2];
            }
        }
        return i2 == cs2.length ? i1 - i2 : -1;
    }

    /*
        求一个字符串每一位之前的字符串最大最长前缀与最长后缀相等时的值
        并且arr[0]=-1 arr[1]=0
     */
    public static int[] getNext(String str) {
        if (str.length() == 1) {
            return new int[]{-1};
        }
        char cs[] = str.toCharArray();
        int[] next = new int[str.length()];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < str.length()) {
            if (cs[cn] == cs[i - 1]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
}
